package Domain;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class DFAConstructor {
	HashMap<DfaState,HashMap<Character,DfaState>> _dfaTable;
	DfaDiagram _dfaDiagram;
	
	public DFAConstructor(NFADiagram n)
	{
		_dfaTable = constructDfaTable(n);
		_dfaDiagram = constructDfaDiagram(_dfaTable);
	}

	public HashMap<DfaState, HashMap<Character, DfaState>> getDfaTable() {
		return _dfaTable;
	}

	public void setDfaTable(
			HashMap<DfaState, HashMap<Character, DfaState>> _dfaTable) {
		this._dfaTable = _dfaTable;
	}
	
	/**
	 * Construct a DFA from an NFA
	 * @param n The NFA to 
	 */
			
	public static LinkedList<Object> doSomething(NfaState n)
	{
		Queue<NfaState> open = new LinkedList();
		NfaState nfaCur = new NfaState();
		DfaState dfaCur;
		LinkedHashMap<NfaState,LinkedHashMap<Character,DfaState>> lut = new LinkedHashMap();
		LinkedHashMap<Character,LinkedHashMap<DfaState,DfaState>> dfaTable = new LinkedHashMap();
		Set<Character> sigma = new HashSet();
		
		open.add(n);
		
		// build the lookup table
		
		LinkedList<NfaState> used = new LinkedList<NfaState>();
		
		
		used = new LinkedList<NfaState>();
		LinkedList<StateTransition> used2 = new LinkedList<StateTransition>();
		LinkedList<StateTransition> st = new LinkedList<StateTransition>();
		used.add(n);
		DfaState dfaEntry = new DfaState();
		dfaEntry.setId("0");
		while((nfaCur = open.poll()) != null) {
			used.add(nfaCur);
			for (StateTransition t : nfaCur.getTransitions()) {
				
				
				if(t.getTransition() == (char)0) 
				{
					if(!used.contains((NfaState)t.getEnd()))
					{	open.add((NfaState)t.getEnd());
					if(t.getEnd().isTerminal())
						dfaEntry.setTerminal(true);
					}
					
				}
				else
				{
					dfaEntry.addNfaState((NfaState)t.getStart());
					if(t.getStart().isTerminal())
						dfaEntry.setTerminal(true);
				}
			}
		}
		
		Queue<DfaState> dfaqueue = new LinkedList();
		dfaqueue.add(dfaEntry);
		//System.out.println(dfaEntry);
		while((dfaCur = dfaqueue.poll()) != null)
		{
			Set<NfaState> states = dfaCur.getSetOfStates();
			//used.add(dfaCur);
			
			st = new LinkedList<StateTransition>();
			for(NfaState s:states)
				{
				//System.out.print("State:" +s+s.getTransitions().size());
				for(StateTransition st1:s.getTransitions())	
					st.add(st1);
					
				
				if(s.isTerminal())
						dfaCur.setTerminal(true);
				}
			
			StateTransition temp;
			DfaState tempst;
		//	System.out.println("dfasizeinit"+st.size());
			while(!st.isEmpty())
			{
				
				//System.out.println("dfasize"+st.size());
				temp = st.removeFirst();
				tempst = getDfaState((NfaState)temp.getEnd());
			//	System.out.println("tempst"+temp.getTransition()+tempst.getSetOfStates().size());
				if(tempst.getSetOfStates().size()==0)
				{
					if(tempst.isTerminal())
					{
						//newTrans = new StateTransition(dfaCur,tempst,temp.getTransition());
						//dfaCur.addTransition(newTrans);
						//dfaCur.setTerminal(true);
						if(!dfaTable.containsKey(temp.getTransition()))
						{
							dfaTable.put(temp.getTransition(), new LinkedHashMap<DfaState,DfaState>());
						}
						LinkedHashMap<DfaState,DfaState> in = dfaTable.get(temp.getTransition());
						//System.out.println("CONTINUING");
						in.put(dfaCur, tempst);
						
						dfaTable.put(temp.getTransition(), in);
						
						continue;
					}
				}
				
				for(int i=0;i<st.size();i++)
				{
					StateTransition check = st.get(i);
					if(temp.getTransition()==check.getTransition())
					{
						st.remove(i);
						i--;
						DfaState tempst1 = getDfaState((NfaState)check.getEnd());
						//System.out.println("skj"+temp.getTransition());
						if(!tempst1.equals(tempst))
						{
							HashSet<NfaState> first = new HashSet<NfaState>();
							first.addAll(tempst1.getSetOfStates());
							first.removeAll(tempst.getSetOfStates());
							tempst.getSetOfStates().addAll(first);
						}
						st.remove(check);
					}
					
				}
				
				
				
				LinkedHashMap<DfaState,DfaState> newValue;
				if(!dfaTable.containsKey(temp.getTransition()))
				{
					dfaTable.put(temp.getTransition(), new LinkedHashMap<DfaState,DfaState>());
				}
				newValue = dfaTable.get(temp.getTransition());
				boolean contains = false;
				/*newValue = dfaTable.get(temp.getTransition());
				for(DfaState f:newValue.keySet())
				{
					if(f.equals(dfaCur))
						{contains = true;dfaCur = f;}
				}
				if(!contains)
				{
					System.out.println("SAMESAME");
					newValue.put(dfaCur, dfaCur);
					dfaTable.put(temp.getTransition(), newValue);
				}*/
				if(dfaCur.equals(tempst))
				{	
						
						for(DfaState f:newValue.keySet())
						{
							if(f.equals(dfaCur))
								{contains = true;dfaCur=f;}
						}
					//	newTrans = new StateTransition(dfaCur,dfaCur,temp.getTransition());
					//	dfaCur.addTransition(newTrans);
						newValue.put(dfaCur, dfaCur);
						dfaTable.put(temp.getTransition(), newValue);
						
					//System.out.println("same");
					
					
				}
				else
				{
					//newTrans = new StateTransition(dfaCur,tempst,temp.getTransition());
					//dfaCur.addTransition(newTrans);
						
						
						//newTrans = new StateTransition(dfaCur,tempst,temp.getTransition());
						
					//dfaCur.addTransition(newTrans);
					contains = false;
					for(DfaState f:newValue.keySet())
					{
						if(f.equals(dfaCur))
							{contains = true;dfaCur=f;}
					}
					//newValue.put(dfaCur, tempst);
						//dfaTable.put(temp.getTransition(), newValue);
					
					/*boolean contains = false;
					for(DfaState s:used2)
					{
						if(s.equals(tempst))
							contains = true;
					}
					if(!contains)
						{*/
						boolean contains1 = false;
						for(DfaState f:newValue.keySet())
						{
							if(f.equals(tempst))
								{contains1 = true;tempst=f;}
						}
						if(!contains1)
							{
							dfaqueue.add(tempst);
							newValue.put(dfaCur,tempst);
							dfaTable.put(temp.getTransition(), newValue);
							//System.out.println("addingqueue"+dfaCur);//}
							
						}
						else{
						newValue.put(dfaCur,tempst);
						dfaTable.put(temp.getTransition(), newValue);}
				}
				
			}
			
			//System.out.println("DFATRANSSIZE:"+dfaCur.getTransitions().size()+"isterm"+dfaCur.isTerminal());
			
		}
		LinkedList<Object> retval = new LinkedList<Object>();
		retval.add(dfaEntry);
		retval.add(dfaTable);
		return retval;
	}
	
	public static DfaState getDfaState(NfaState n)
	{
		LinkedList<NfaState> used = new LinkedList<NfaState>();
		Queue<NfaState> open = new LinkedList();
		NfaState nfaCur;
		DfaState dfaEntry = new DfaState();
		open.add(n);
		while((nfaCur = open.poll()) != null) {
			used.add(nfaCur);
			for (StateTransition t : nfaCur.getTransitions()) {
				
			
				if(t.getTransition() == (char)0) 
				{
					if(!used.contains((NfaState)t.getEnd()))
					{	open.add((NfaState)t.getEnd());
					if(t.getEnd().isTerminal())
						dfaEntry.setTerminal(true);
					}
					
				}
				else
				{
					dfaEntry.addNfaState((NfaState)t.getStart());
					if(t.getStart().isTerminal())
						dfaEntry.setTerminal(true);
				}
			}
		}
		
		return dfaEntry;
	}
	private static HashMap<DfaState,HashMap<Character,DfaState>> constructDfaTable(NFADiagram n) {
		// create lookup table for NFA State transitions
		HashMap<NfaState,HashMap<Character,DfaState>> lut = new HashMap();

		// create a table that maps a DfaState to a row, each of which maps a Character to a DfaState
		HashMap<DfaState,HashMap<Character,DfaState>> dfaTable = new HashMap();
		
		// Alphabet
		Set<Character> sigma = new HashSet();
		
		// the open list is the list of states that have not been added to the LUT already
		Queue<NfaState> open = new LinkedList();
		open.add(n.getNfaStart());
		
		// build the lookup table
		NfaState nfaCur;
		while((nfaCur = open.poll()) != null) {
			HashMap<Character,DfaState> row = new HashMap();
			DfaState dfaEntry = new DfaState();
			
			for (StateTransition t : nfaCur.getTransitions()) {
				// ensure endpoint either has been explored or is added to the queue
				if(!lut.containsKey(t.getEnd())) {
					open.add((NfaState)t.getEnd());
					
				}
				
				// only add entries corresponding to a letter in the alphabet
				if(t.getTransition() == (char)0) continue;
				
				sigma.add(t.getTransition());
				
				AddEpsilonClosure((NfaState)t.getEnd(), dfaEntry);
				
				row.put(t.getTransition(), dfaEntry);		
				
			}
			lut.put(nfaCur, row);
		}		
		
		// create the initial state of the DFA from the start of the NFA diagram
		// and any states that it has an epsilon-transition to
		DfaState initialState = new DfaState();
		initialState.setId("0");
		AddEpsilonClosure(n.getNfaStart(),initialState);
				
		// start building DFA states
		Queue<DfaState> dfaOpen = new LinkedList();
		dfaOpen.add(initialState);
		DfaState dfaCur;
		// while there's dfa states yet to be explored
		while((dfaCur = dfaOpen.poll()) != null) {
			HashMap<Character,DfaState> row = new HashMap();
			
			// for each character in the alphabet, create an entry, then iterate through
			// all the Nfa States in the Dfa state and look them up in lut
			for(Character c : sigma) {
				DfaState dfaEntry = new DfaState();
				
				for(NfaState ns : dfaCur.getSetOfStates()) {
					DfaState lutEntry = lut.get(ns).get(c);
					if(lutEntry == null) continue;
					
					// if there's a lut entry, union it to the new Dfa Entry
					for(NfaState tempns : lutEntry.getSetOfStates()) {
						dfaEntry.addNfaState(tempns);
						
						// mark the dfa state as terminal if it contains a terminal NFA state
						if(tempns.isTerminal())
							dfaEntry.setTerminal(true);
					}
				}
				
				// go through the state table to see if this state has been
				// added already
				// if it has, associate dfaEntry with the reference in the table
				// to minimize memory use
				// otherwise, add dfaEntry to the open list
				boolean inTable = false;
				for(DfaState stateInTable : dfaTable.keySet()) {
					if(dfaEntry.equals(stateInTable)) {
						dfaEntry = stateInTable;
						inTable = true;
						break;
					}
				}
				if(!inTable){
					dfaOpen.add(dfaEntry);
				}

				row.put(c, dfaEntry);
			}
			
			dfaTable.put(dfaCur, row);
		}
		
		return dfaTable;
	}


	public DfaDiagram constructDfaDiagram(HashMap<DfaState,HashMap<Character,DfaState>> table) {
		DfaDiagram diagram = new DfaDiagram();
		
		// this would be easier after minimization because there's guaranteed to only be one terminal state
		for(DfaState ds : table.keySet()) {
			for(Character c : table.get(ds).keySet()) {
				StateTransition t = new StateTransition();
				t.setStart(ds);
				t.setEnd(table.get(ds).get(c));
				t.setTransition(c);
				ds.addTransition(t);
			}
		}
		return diagram;
	}
	
	/**
	 * Adds the Epsilon Closure of the NFA state to the DFA state
	 * @param s
	 * @param dfaEntry
	 */
	private static void AddEpsilonClosure(NfaState s, DfaState dfaEntry) {
		dfaEntry.addNfaState(s);
		for(StateTransition t : s.getTransitions()) {
			if(t.getTransition() == (char)0 && !dfaEntry.getSetOfStates().contains(t.getEnd())) {
				AddEpsilonClosure((NfaState)t.getEnd(),dfaEntry);
			}
		}
	}



	//for testing
	public static void main(String[] args)
	{
		
	}

}